The present invention relates to frame-multiplexed data communications networks, in general, and more particularly to a method of and apparatus for allocating memory for the storage of vocabularies used in the adaptive data compression of frame-multiplexed traffic of a data communications network.
Most modern data communications networks include a multiplicity of paths or links which are interconnected to route data traffic from one edge of the network to another. At each edge, there is an interconnect node for coupling a plurality of data sources and data destinations to the network. In some cases, the sources and destinations are first connected to a local area network (LAN) which is then interconnected in the aggregate to the interconnect node. Accordingly, a source of one LAN at one edge of the network may transmit data to a destination of a second LAN located at another edge of the network through their respective interconnect nodes.
Since there generally are a large number of data sources at any given edge which desire to communicate through their respective interconnect node to destinations at various other edges of the network, the data traffic from the various sources is multiplexed through the source interconnect node and then, demultiplexed at the destination interconnect node and delivered to the proper destination point. In most modern systems, data is communicated from a source in a frame unit where each frame unit begins with a frame address ID or header including the source and destination addresses, followed by the data information, and ending with an error correction code, like a CRC code, for example. Accordingly, in these systems, the data traffic from the various sources at the one edge of the network is time-division multiplexed according to the frame units of data. This is commonly referred to as frame-multiplexed data traffic.
The links of the network are rated based on capacity or the rate of data which may be communicated thereover in kilobits per second (kbps), sometimes referred to as link bandwidth. This capacity is fixed for any given link. Some links may have a capacity of 9.6 kbps and others 56 kbps, for example. The user's cost for communicating over the network is based on the link capacity used. That is, it would be much more expensive to use 56 kbps links than the 9.6 kbps links. Therefore, it is the desire of a user to maintain communication over the lower capacity links, even with a higher capacity demand. There are various techniques to achieve an effective capacity of two or three times the fixed capacity of the link thus increasing throughput efficiency of the lower capacity link to accommodate the higher capacity demand. One technique for accomplishing an increased perceived capacity is through use of data compression as described in the paper: G. Held, "Expanding the Uses of Data Compression," Data Communications, pp. 149-156, June 1984".
As explained by the above referenced paper, frame multiplexed traffic is traditionally compressed by either of two methods. The first method encodes the aggregate frame-multiplexed data stream as it flows through the interconnect node like it was a single homogeneous channel, that is all coming from the same source and going to the same destination. The second method which is considered more efficient compresses the data at the terminal port level of each data source before being multiplexed through the interconnect node of the network. The decompression takes place after the demultiplexing at the remote edge of the network.
In general, frame multiplexed data is less compressible in the aggregate than its frame components because of differences in statistical characteristics among the various channels or source/destination pairs. Thus, compressing the frame data separately for each source provides higher compression efficiency. For frame multiplexed traffic, the performance of the first method relies heavily on the frame size. It degrades to unacceptable levels if frames are too short. On the other hand, the second method performs independently of the multiplexing schemes, but depends on accessibility to the data before multiplexing, i.e. at the terminal port level of the node for each source.
Data compression encoding is usually accomplished by some adaptive method in which the encoder adapts to the statistics of the aggregate data as it passes through the encoder. In so doing, the encoder gathers statistics, referred to as the data compression vocabulary which it stores in a dedicated volatile memory space. Both the encoder and decoder continuously update their vocabularies based on the current data being communicated. In the aggregate data compression method, only one vocabulary is presently being used and updated at both the encoder and decoder of the source and destination interconnect nodes, respectively. However, in the second method of data compression, a separate vocabulary is kept for each terminal port of a data source.
The use of a single vocabulary shared among the various terminal ports of an interconnect node and adapted according to the data being communicated therethrough appears rather attractive. However, in most data compression encoders, the data compression vocabulary adapts itself to specific sequence of characters, numbers, symbols, probabilities, or the like of a frame which is currently being encoded. Accordingly, the data compression efficiency of a single shared vocabulary is based on the type of data being multiplexed from the sources of an interconnect node. If all of the sources are transmitting the same type of data, e.g. all text or all numbers, then the single shared vocabulary will adapt itself to provide a rather good compression efficiency ratio. On the other hand, if there are different types of data being frame-multiplexed through the encoder, then the overhead operations associated with the adaptive compression processing may cause the efficiency ratio to be less than one, that is actually worse than if the data was passed uncompressed, in some cases. Accordingly, in such systems one could expect a very poor compression ratio overall.
Since most networks include data sources transmitting a wide variety of data through each interconnect node, it is believed of paramount importance to include a plurality of vocabularies to maintain an acceptable data compression efficiency. If each interconnect node of the network had an unlimited memory resource, then a different portion of the memory could be allocated for each possible vocabulary. But, since memory is a limited resource at each node, this is not a practical solution. Accordingly, it is the intent of the present invention to provide for the various vocabularies needed to satisfy all of the source/destination communications of each interconnect node at an acceptable data compression efficiency with the limited available memory thereof.